package problems.daily;

import java.util.*;

/**
 * 1129. 颜色交替的最短路径
 * <p>https://leetcode.cn/problems/shortest-path-alternating-colors/</p>
 *
 * @author habitplus
 * @since 10:06, 2023/2/2
 */
public class DT1129 {
    public int[] shortestAlternatingPaths(int n, int[][] redEdges, int[][] blueEdges) {
        List<Integer>[][] next = new List[2][n];

        for (int i = 0; i < 2; ++i) {
            for (int j = 0; j < n; ++j) {
                next[i][j] = new ArrayList<>();
            }
        }

        for (int[] e : redEdges) {
            next[0][e[0]].add(e[1]);
        }

        for (int[] e : blueEdges) {
            next[1][e[0]].add(e[1]);
        }

        // 记录两种类型的颜色最短路径的长度
        int[][] dist = new int[2][n];
        for (int i = 0; i < 2; ++i) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        Queue<int[]> que = new LinkedList<>();
        int[] pair;
        int s, c;
        dist[0][0] = 0;
        dist[1][0] = 0;
        que.offer(new int[]{0, 0});
        que.offer(new int[]{0, 1});

        while (!que.isEmpty()) {
            pair = que.poll();
            s = pair[0];
            c = pair[1];

            for (int e : next[1 - c][s]) {
                if (dist[1 - c][e] != Integer.MAX_VALUE) {
                    continue;
                }
                dist[1 - c][e] = dist[c][s] + 1;
                que.offer(new int[]{e, 1 - c});
            }
        }

        int[] ret = new int[n];
        for (int i = 0; i < n; ++i) {
            ret[i] = Math.min(dist[0][i], dist[1][i]);
            if (ret[i] == Integer.MAX_VALUE) {
                ret[i] = -1;
            }
        }

        return ret;
    }
}
